1. Field of the Invention
This invention relates generally to the field of network diagnostic and management systems for communications network and a method and apparatus for displaying the results of database queries. More particularly the present invention relates to a method and device for determining the interconnection topology of a possible dynamic data communication network and for conducting communication between a network controller and the devices being controlled. The invention uses an unique method of querying a database which permits a graphical representation of the query results.
2. Background of the Invention
Relational database software is commercially available and suitable for various database functions where elements of the database are related to one another in some way. For example, such databases may be used to store information about a company's employees. Such information may include structural relationships concerning a person's position within a company's organization such as the person's department name or number, his supervisor, his subordinates, etc. Traditional relational database managers are able to readily produce, for example, a list of all of the people who report to a particular supervisor. Unfortunately, this method of displaying relational information is often not optimal for use by the database user. For example, although such information may provide a complete structural definition of a company's organizational structure, a graphical representation such as the typical organization chart is much more easily digested by the human user.
In an environment more closely akin to the preferred embodiment, it becomes even more evident that the typical database output format is inferior. Consider, for example, a major airline's telecommunication system for data communication used for processing reservations. The network's topology may be stored in a relational database containing entries which are related to one another by their interconnection. However, present relational database management software provides no mechanism for displaying that interconnection in a manner which is easily understood. Such software typically is only able to provide a sorted listing selected entries of the database.
Such a data communications network consists of nodes and links. The nodes are of different types and can offer different services. A node has a set of ports, and a set of time varying mappings are defined between these ports. Nodes are connected to form the network via links. Links connect the external ports of the nodes. The network derives its time varying character by virtue of the switching that takes place in the nodes. The network carries user data in logical pipes called channels. The channels are dynamic and the physical paths followed by the channel can change with time. The channel data flows change as a result of this switching. A multiplicity of channels may be carried by a link.
Each node receives the data on its ports and forwards it on some other port(s) depending on the switching state of the node. Data from a multiplicity of ports may be sent on a single port and vice versa.
For several reasons including network management it is required that network topology and channel flow changes can be represented, displayed, and effected in an efficient manner. In particular it is required from the network management perspective to effect configuration and switching changes, run diagnostic tests on the nodes and links and to receive unsolicited information regarding the spontaneous activity in the network. Several management entitles can simultaneously control the network. In such complex networks, it is also desirable to be able to display selected portions or views of the network in a graphical manner which is better digested by the user.
U.S. Pat. No. 4,613,946 to Forman describes a method and apparatus for generating hierarchical displays. But, only the entire tree, or the entire portion of a tree beginning at a selected root node may be selected for display.
Hitherto, in literature several search techniques have been proposed. Examples include Winston, P.H."Examples Involving Search", LISP, pp. 137-154, Addison-Wesley Publishing Co., 1984; Winston, P.H., "Exploring Alternatives", Artificial Intelligence, pp. 87-136, Addison-Wesley Publishing Co., 1984; and Aho A.V. et at., "Directed Graphs", Data Structures and Algorithms, pp. 198-229 Addison Wesley Publishing Co., 1982. However, these techniques use a model of the node where input on any port can go out on any other port. No attempt is made to model the internal characteristics of the node. Furthermore the time varying aspect of the internal switchings is not modelled.
There are elegant algorithms for directed tree searches, but in absence of internal node modelling, flood routing such as described in U.S. Pat. No. 4,399,531 to Grande et al. seems to be the norm for searching in undirected graphs.
Since different networks have different characteristics, an efficient and generic method is needed to handle all the various network types uniformly in order to:
determine the configuration topology based on services and channels; PA1 determine routing between two nodes; PA1 search the management entity controlling the node (management entity can change dynamically); PA1 determine channels carried by the node; and PA1 search for different services and node types.
A model for connectivity of these objects is needed and a search algorithm is also needed for obtaining routes and views of the connectivity of the network. The search algorithm should be capable of tracing logical connection pathways referred to here as channels in an efficient manner by pruning the undesired pathways.
The present invention satisfies these needs by utilizing a mechanism for modelling the internal switchings of a node as well as routing mechanisms to perform efficient searches in face of time varying dynamic behavior of the network, which is a characteristic of most data communication networks.
The present invention also provides a mechanism to display graphically a representation of a relational database and provides a mechanism for searching a complex computer network for a particular device within the network so that control over that device may be effected by a network controller. The search is conducted in an efficient manner which relies upon a network model which may simulate any element in a communication network.